/* 判断一个二叉树是否为平衡二叉树 */
#include <iostream>
#include "BiTree.h"
using namespace std;

// 判断是否为平衡二叉树，balance是判断标记，n是树的高度
void fun(BTNode *bt, int &balance, int &h)
{
  int bl = 0, br = 0, hl = 0, hr = 0;
  
  // 二叉树为空
  if (bt == NULL)
  {
    h = 0;
    balance = 1; // 属于平衡二叉树
  }
  
  // 二叉树只有一个根结点
  else if (!bt->lchild && !bt->rchild)
  {
    h = 1;
    balance = 1; // 属于平衡二叉树
  }
  
  // 
  else
  {
    // 判断左子树是否为平衡二叉树
    fun(bt->lchild, bl, hl);
    
    // 判断右子树是否为平衡二叉树
    fun(bt->rchild, br, hr);
    
    // 记录二叉树的高度
    h = (hl > hr ? hl : hr) + 1;
    
    // 计算左子树与右子树的高度差
    if (abs(hl - hr) < 2)
      balance = bl && br;
    else
      balance = 0;
  }
}
int main()
{
  // 创建二叉树
  BTNode *T = create_BiTree();
  
  // 判断是否为平衡二叉树
  int balance = 0, h = 0;
  fun(T, balance, h);
  
  // 输出
  cout << balance;
  return 0;
}